package com.zhengb.algorithmdemo.leetcode.linklist;

/**
 * Created by zhengbo on 2020/4/28.
 */
public class MyLinkedList {

    private static class LinkNode<T> {

        public T data;

        public LinkNode<T> preNode;

        public LinkNode<T> nextNode;

        LinkNode(T data) {
            this.data = data;
        }
    }

    private LinkNode<Integer> headNode;

    private LinkNode<Integer> tailNode;

    private int nodeCount;

    /**
     * Initialize your data structure here.
     */
    public MyLinkedList() {

    }

    private LinkNode<Integer> findNodeByIndex(int index) {
        LinkNode<Integer> curNode = headNode;

        for (int i = 0; i < index; i++) {
            if (curNode == null) {
                return null;
            }
            curNode = curNode.nextNode;
        }
        return curNode;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        if (headNode == null) {
            return -1;
        }

        if (index == 0) {
            return headNode.data;
        }

        LinkNode<Integer> nodeByIndex = findNodeByIndex(index);

        if (nodeByIndex != null) {
            return nodeByIndex.data;
        }
        return -1;
    }

    /**
     * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(int val) {

        LinkNode<Integer> insertNode = new LinkNode<>(val);
        if (headNode == null) {
            headNode = insertNode;
            tailNode = insertNode;
        } else {
            insertNode.nextNode = headNode;
            insertNode.preNode = null;

            headNode.preNode = insertNode;

            headNode = insertNode;
        }
        nodeCount++;
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {

        LinkNode<Integer> newNode = new LinkNode<>(val);

        if (tailNode == null) {
            headNode = newNode;
            tailNode = newNode;
        } else {
            tailNode.nextNode = newNode;
            newNode.preNode = tailNode;

            tailNode = newNode;
        }
        nodeCount++;
    }

    /**
     * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,
     * the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        }

        if (index == nodeCount) {
            addAtTail(val);
            return;
        }
        if (index > nodeCount) {
            return;
        }

        LinkNode<Integer> findNode = findNodeByIndex(index);

        if (findNode == null) {
            return;
        }
        LinkNode<Integer> newNode = new LinkNode<>(val);

        LinkNode<Integer> preNode = findNode.preNode;

        newNode.preNode = preNode;
        newNode.nextNode = findNode;

        preNode.nextNode = newNode;
        findNode.preNode = newNode;

        nodeCount++;
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {

        if (headNode == null) {
            return;
        }
        LinkNode<Integer> findNode = findNodeByIndex(index);
        if (findNode == null) {
            return;
        }

        LinkNode<Integer> preNode = findNode.preNode;
        LinkNode<Integer> nextNode = findNode.nextNode;

        if (preNode == null && nextNode == null) {
            tailNode = null;
            headNode = null;
            nodeCount--;
            return;
        }

        if (preNode != null && nextNode != null) {
            preNode.nextNode = nextNode;
            nextNode.preNode = preNode;
        }
        //删除头结点
        if (preNode == null) {
            nextNode.preNode = null;
            headNode = nextNode;
        }
        //删除尾节点
        if (nextNode == null) {
            preNode.nextNode = null;
            tailNode = preNode;
        }
        nodeCount--;
    }

    public static void main(String[] args) {

        MyLinkedList linkedList = new MyLinkedList();
//        linkedList.addAtHead(1);
//        linkedList.addAtTail(3);
//        linkedList.addAtIndex(1, 2);   //链表变为1-> 2-> 3
//        System.out.println(linkedList.get(1));//返回2
//        linkedList.deleteAtIndex(1);  //现在链表是1-> 3
//        System.out.println(linkedList.get(1));//返回3

        //["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex",
        // "addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]
        //[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]

//        linkedList.addAtHead(7);
//        linkedList.addAtHead(2);
//        linkedList.addAtHead(1);
//        linkedList.addAtIndex(3, 0);
//        linkedList.deleteAtIndex(2);
//        linkedList.addAtHead(6);
//        linkedList.addAtTail(4);
//        System.out.println(linkedList.get(4));
//        linkedList.addAtHead(4);
//        linkedList.addAtIndex(5, 0);
//        linkedList.addAtHead(6);


        linkedList.addAtHead(1);

        linkedList.deleteAtIndex(0);


//        linkedList.addAtIndex(0, 10);
//        linkedList.addAtIndex(0, 20);
//        linkedList.addAtIndex(1, 30);
//        linkedList.get(0);

        //"addAtHead","get","addAtTail","deleteAtIndex","get",
//        linkedList.addAtHead(24);
//        System.out.println(linkedList.get(1));
//        linkedList.addAtTail(18);
//        linkedList.deleteAtIndex(1);
//        System.out.println(linkedList.get(1));


    }
}
